import java.util.*;
import java.util.regex.*;
import java.text.*;
import java.math.*;
import java.awt.geom.*;

public class PermissionTree {
	public Node root;

	public int[] findHome(String[] folders, String[] users) {
		int[] ret = new int[users.length];
		root = init(folders);
		// display(root);
		for (int i = 0; i < users.length; i++) {
			ret[i] = find(root, users[i]);
		}
		return ret;
	}

	public void display(Node node) {
		System.out.print(node.id + " : ");
		for (int i = 0; i < node.users.size(); i++)
			System.out.print(node.users.get(i) + ", ");
		System.out.println();
		for (int i = 0; i < node.next.size(); i++)
			display(node.next.get(i));
	}

	public int find(Node node, String s) {
		if (node == null)
			return -1;
		if (node.users.indexOf(s) != -1)
			return node.id;
		int count = 0;
		int id = -1;
		for (int i = 0; i < node.next.size(); i++) {
			int tmp = find(node.next.get(i), s);
			if (tmp != -1) {
				count++;
				id = tmp;
			}
		}
		if (count == 1)
			return id;
		if (count > 1)
			return node.id;
		return -1;
	}

	public Node init(String[] folders) {
		List<Node> list = new ArrayList<Node>();
		for (int i = 0; i < folders.length; i++) {
			list.add(new Node());
		}
		for (int i = 0; i < folders.length; i++) {
			list.get(i).id = i;
			int id = Integer.parseInt(folders[i].split(" ")[0]);
			// not self node.
			if (id != i) {
				list.get(id).next.add(list.get(i));
			}
			String[] names = folders[i].split(" ")[1].split(",");
			for (int j = 0; j < names.length; j++)
				list.get(i).users.add(names[j]);
		}
		return list.get(0);
	}
	 public static void main(String[] args)
	{
		long time;
		int[] answer;
		boolean errors = false;
		int[] desiredAnswer;
		
		boolean same;
		
		time = System.currentTimeMillis();
		answer = new PermissionTree().findHome(new String[]{"0 Admin", "0 Joe,Phil", "0 Joe"}, new String[]{"Admin", "Joe", "Phil"});
		System.out.println("Time: " + (System.currentTimeMillis()-time)/1000.0 + " seconds");
		desiredAnswer = new int[]{ 0,  0,  1 };
		System.out.println("Your answer:");
		if (answer.length > 0)
		{
			System.out.print("\t{ " + answer[0]);
			for (int i=1; i<answer.length; i++)
				System.out.print(", " + answer[i]);
			System.out.println(" }");
		}
		else
			System.out.println("\t{ }");
		System.out.println("Desired answer:");
		if (desiredAnswer.length > 0)
		{
			System.out.print("\t{ " + desiredAnswer[0]);
			for (int i=1; i<desiredAnswer.length; i++)
				System.out.print(", " + desiredAnswer[i]);
			System.out.println(" }");
		}
		else
			System.out.println("\t{ }");
		same = desiredAnswer.length == answer.length;
		for (int i=0; i<answer.length && same; i++)
			if (answer[i] != desiredAnswer[i])
				same = false;
		if (!same)
		{
			errors = true;
			System.out.println("DOESN'T MATCH!!!!");
		}
		else
			System.out.println("Match :-)");
		System.out.println();
		time = System.currentTimeMillis();
		answer = new PermissionTree().findHome(new String[]{"0 Admin"}, new String[]{"Peter", "Paul", "Mary"});
		System.out.println("Time: " + (System.currentTimeMillis()-time)/1000.0 + " seconds");
		desiredAnswer = new int[]{ -1,  -1,  -1 };
		System.out.println("Your answer:");
		if (answer.length > 0)
		{
			System.out.print("\t{ " + answer[0]);
			for (int i=1; i<answer.length; i++)
				System.out.print(", " + answer[i]);
			System.out.println(" }");
		}
		else
			System.out.println("\t{ }");
		System.out.println("Desired answer:");
		if (desiredAnswer.length > 0)
		{
			System.out.print("\t{ " + desiredAnswer[0]);
			for (int i=1; i<desiredAnswer.length; i++)
				System.out.print(", " + desiredAnswer[i]);
			System.out.println(" }");
		}
		else
			System.out.println("\t{ }");
		same = desiredAnswer.length == answer.length;
		for (int i=0; i<answer.length && same; i++)
			if (answer[i] != desiredAnswer[i])
				same = false;
		if (!same)
		{
			errors = true;
			System.out.println("DOESN'T MATCH!!!!");
		}
		else
			System.out.println("Match :-)");
		System.out.println();
		time = System.currentTimeMillis();
		answer = new PermissionTree().findHome(new String[]{"0 Admin", "2 John", "0 Peter,John", "0 Tim", "1 John"}, new String[]{"John"});
		System.out.println("Time: " + (System.currentTimeMillis()-time)/1000.0 + " seconds");
		desiredAnswer = new int[]{ 2 };
		System.out.println("Your answer:");
		if (answer.length > 0)
		{
			System.out.print("\t{ " + answer[0]);
			for (int i=1; i<answer.length; i++)
				System.out.print(", " + answer[i]);
			System.out.println(" }");
		}
		else
			System.out.println("\t{ }");
		System.out.println("Desired answer:");
		if (desiredAnswer.length > 0)
		{
			System.out.print("\t{ " + desiredAnswer[0]);
			for (int i=1; i<desiredAnswer.length; i++)
				System.out.print(", " + desiredAnswer[i]);
			System.out.println(" }");
		}
		else
			System.out.println("\t{ }");
		same = desiredAnswer.length == answer.length;
		for (int i=0; i<answer.length && same; i++)
			if (answer[i] != desiredAnswer[i])
				same = false;
		if (!same)
		{
			errors = true;
			System.out.println("DOESN'T MATCH!!!!");
		}
		else
			System.out.println("Match :-)");
		System.out.println();
		time = System.currentTimeMillis();
		answer = new PermissionTree().findHome(new String[]{"0 Admin","0 Jeff", "1 Mark,Tim", "1 Tim,Jeff","0 Dan", "4 Ed", "4 Tom", "4 Kyle,Ed","0 Ben", "8 Rich", "8 Sam", "8 Tim"}, new String[]{"Jeff", "Ed", "Tim", "Steve"});
		System.out.println("Time: " + (System.currentTimeMillis()-time)/1000.0 + " seconds");
		desiredAnswer = new int[]{ 1,  4,  0,  -1 };
		System.out.println("Your answer:");
		if (answer.length > 0)
		{
			System.out.print("\t{ " + answer[0]);
			for (int i=1; i<answer.length; i++)
				System.out.print(", " + answer[i]);
			System.out.println(" }");
		}
		else
			System.out.println("\t{ }");
		System.out.println("Desired answer:");
		if (desiredAnswer.length > 0)
		{
			System.out.print("\t{ " + desiredAnswer[0]);
			for (int i=1; i<desiredAnswer.length; i++)
				System.out.print(", " + desiredAnswer[i]);
			System.out.println(" }");
		}
		else
			System.out.println("\t{ }");
		same = desiredAnswer.length == answer.length;
		for (int i=0; i<answer.length && same; i++)
			if (answer[i] != desiredAnswer[i])
				same = false;
		if (!same)
		{
			errors = true;
			System.out.println("DOESN'T MATCH!!!!");
		}
		else
			System.out.println("Match :-)");
		System.out.println();
		time = System.currentTimeMillis();
		answer = new PermissionTree().findHome(new String[]{"0 Admin", "0 Bob,Joe,Bob", "0 Joe"}, new String[]{"Joe", "Bob"});
		System.out.println("Time: " + (System.currentTimeMillis()-time)/1000.0 + " seconds");
		desiredAnswer = new int[]{ 0,  1 };
		System.out.println("Your answer:");
		if (answer.length > 0)
		{
			System.out.print("\t{ " + answer[0]);
			for (int i=1; i<answer.length; i++)
				System.out.print(", " + answer[i]);
			System.out.println(" }");
		}
		else
			System.out.println("\t{ }");
		System.out.println("Desired answer:");
		if (desiredAnswer.length > 0)
		{
			System.out.print("\t{ " + desiredAnswer[0]);
			for (int i=1; i<desiredAnswer.length; i++)
				System.out.print(", " + desiredAnswer[i]);
			System.out.println(" }");
		}
		else
			System.out.println("\t{ }");
		same = desiredAnswer.length == answer.length;
		for (int i=0; i<answer.length && same; i++)
			if (answer[i] != desiredAnswer[i])
				same = false;
		if (!same)
		{
			errors = true;
			System.out.println("DOESN'T MATCH!!!!");
		}
		else
			System.out.println("Match :-)");
		System.out.println();
		
		
		if (errors)
			System.out.println("Some of the test cases had errors :-(");
		else
			System.out.println("You're a stud (at least on the test data)! :-D ");
	}

}

class Node {
	public int id;
	public List<String> users;
	public List<Node> next;

	public Node() {
		this.id = -1;
		this.users = new ArrayList<String>();
		this.next = new ArrayList<Node>();
	}
}

// Powered by [KawigiEdit] 2.0!
